from typing import List


class Solution:
    def medianOfUniquenessArray(self, nums: List[int]) -> int:
        result = {}
        maxLen = int(len(nums)/2) + 1
        median = (1 + len(nums)) * len(nums) / 4
        for i in range(1, len(nums)+1):
            maxLen = addNum(nums, i, result, maxLen, median)


        # print("median:", median)
        for i in range(1, int(len(nums)/2) + 1):
            if median - result[i] <= 0:
                return i
            else:
                median = median - result[i]
        return int(len(nums)/2) + 1

def addNum(nums:  List[int], maxIndex: int, lastResult: dict[int, int], maxLen, median)->int:
    # print("add:", nums[len(nums) - 1])
    tmp = {}
    tmpCount = 0
    for i in range(maxIndex, 0, -1):
        # print("tmp:", nums[i-1])
        tmp[nums[i-1]] = True
        old = lastResult.get(len(tmp))
        if  old is None:
            old = 0
        lastResult[len(tmp)] =  old + 1
        # print("lastResult:", lastResult)
        tmpCount += lastResult[len(tmp)]
        if tmpCount > median:
            maxLen = len(tmp)
        if len(tmp) > maxLen:
            # print("maxLen:", maxLen, len(tmp))
            break
    # print("end lastResult:", lastResult)
    return maxLen


if __name__ == '__main__':
    nums = [88, 28, 3, 21, 89, 59, 21]
    # nums = [76847,99468,37237,10525,66967,22759,31896,19060,53532,35992,61115,41621,92942,58066,17210,44740,44800,12884,48742,70686,71789,28309,56928,41848,12595,23130,84683,69425,97317,40107,30772,68112,72867,32484,36952,48405,90367,24962,42707,83951,92468,34226,7290,15068,15246,80442,21075,52743,4053,17133,29066,30015,14769,82981,13349,162,93717,68216,6429,38111,13269,75206,65884,27903,14089,22144,86766,62371,87691,65103,49333,17580,63240,17257,16378,23264,35074,26170,97310,2849,56047,72696,85351,90227,43362,11348,97404,24379,17280,72265,39894,40722,29331,46251,44347,38237,31986,91324,84821,1300,48018,42915,13118,88543,78856,67207,70949,51444,63002,54979,66534,93339,47858,52625,15686,45272,12783,11863,38106,10786,97906,89508,89608,98737,64779,46137,15417,44386,81051,94779,53121,70876,61866,19906,91173,13700,32306,50426,44264,61433,17100,94303,15955,39255,99527,90757,54295,32374,86826,91197,76123,37394,73224,71742,62855,11174,2584,34870,60151,54170,44078,79263,59692,47418,99403,17713,55694,91966,91724,26343,5212,34436,32659,31609,65440,48717,83986,94306,16620,90932,64903,32186,1208,94646,95013,1715,68954,58793,77468,58494,69035,2690,72398,39763,12043,17135,63114,72302,88620,13575,33762,92645,26101,64642,98164,60710,78325,23909,1046,49217,95833,42542,96160,94938,70820,70625,71258,35899,76892,15795,84590,65587,34246,21571,13796,93735,99679,89433,12664,3229,75788,682,95122,37768,1654,90292,97379,43640,63320,33225,30217,32120,95072,13926,129,56902,965,13168,38016,39044,87832,44856,2151,17168,25598,96347,25760,59017,78136,21983,92225,3110,27565,14702,22610,3465,8122,83895,45659,94612,76882,41635,80463,85502,70390,79425,26279,33917,17108,84615,4409,80445,25968,91356,20123,75846,62244,78831,5481,44618,69998,32246,92577,46186,9935,54667,71923,96000,83694,13570,84017,58755,29450,67799,84972,85576,58247,81920,82794,16208,17420,27330,36009,70565,81506,89653,28175,77371,92025,39105,47985,78211,55750,73194,73338,76939,43000,4604,21279,15905,3700,71404,72124,58244,57246,96456,56519,6145,93598,23284,24997,11778,2547,94533,13308,71426,7981,51587,89762,10342,15334,84300,20739,75271,12573,99578,21249,73032,2857,44388,35222,65490,94697,65262,85087,92845,65122,36640,61082,44228,17439,91911,98339,62618,66165,60956,18756,3199,34015,89941,69782,7963,66848,33483,97675,88446,96895,75810,54393,68597,95821,38680,1764,5574,14790,47099,39927,17625,9995,27717,18476,25418,2298,30341,34551,28314,43693,42066,2302,90710,93001,51067,8154,97724,74998,37885,65660,73191,40728,30901,81102,64812,66914,92279,64874,3959,86640,25711,56729,93132,56653,11913,9016,862,5328,15771,35510,65272,68203,5808,9973,56370,68021,26010,54139,51526,65601,61245,388,58004,96511,362,99018,10075,4556,50930,59635,16495,93885,70063,18581,30636,65901,42910,62124,70524,17506,8945,79091,26948,54883,63090,81574,69084,16920,95711,73958,43808,42888,90490,43617,76367,23890,3398,43197,97989,80998,50695,57236,82600,17934,83358,24651,32400,55540,42134,97977,94009,90191,81130,55292,96443,84292,40015,16216,76761,63377,81401,65447,67947,65706,64093,10827,16279,56996,52061,86405,91299,73252,51936,75531,85603,50481,71110,92199,40089,13340,54636,18535,34393,72793,96134,21957,65020,65953,15616,46156,70630,77367,1881,59688,2893,85611,79658,62644,26325,74257,42124,13108,96400,98096,76736,70052,72762,4889,28885,56240,91605,66072,70551,515,36346,28752,31311,71804,3647,21486,42760,42195,29943,44809,34063,51904,78095,66904,39567,65609,56138,22307,5426,82525,17007,88418,49665,43996,6814,61672,38847,98055,73229,98440,67435,58134,52566,53747,3649,67411,54098,84580,79406,3251,23311,55494,35839,82749,8131,61993,77986,98526,43287,93311,25056,48637,57675,64849,19045,43123,1001,99557,26924,68967,43905,93774,81747,96043,24275,78990,98853,53787,15205,21086,83162,30092,33290,6647,19768,23661,44112,89152,66326,9878,32324,19543,83689,47984,3057,32528,53113,29846,53713,7331,605,3975,10130,16885,70489,80499,83810,93051,9581,8242,64573,61087,20253,19365,49979,44495,727,1895,57688,45157,17933,94387,8590,95955,56917,10755,75270,49589,96720,55639,76407,43651,86897,9245,83047,12969,94124,99912,50482,22695,62810,58960,97864,93624,43770,24671,50300,37634,39961,99436,74944,37227,18163,71182,28528,99641,77643,28193,50739,24928,13790,92592,97571,44469,80685,21084,38406,7922,42273,55066,62253,49672,20371,30580,21358,93620,31667,62460,8376,38297,21050,67623,2795,86933,58186,75378,94893,45351,21730,88017,89731,27927,87917,2984,9247,24016,58081,96676,51415,5668,26368,59669,28159,83142,63179,99565,49699,16510,95220,22181,43720,82120,12968,70287,66327,67965,54941,96248,1311,34057,85461,66885,83221,24038,31434,60329,62393,76667,46810,22277,32559,29259,76476,73638,20968,40105,73331,52299,96655,48308,37240,73086,37022,54888,54809,73158,52682,1123,82575,1972,24184,33912,88879,97563,56757,20546,7692,75441,78408,20998,73734,48809,98433,72975,82711,70883,23060,5888,68905,27897,94135,79931,99712,50541,88615,73483,86652,4979,53127,72252,92817,89772,3388,2171,24466,16852,54952,75825,45741,66323,975,74044,72380,55134,97000,4033,63284,83459,34020,55413,48873,55523,7664,86912,71071,30188,5616,28555,60761,74653,92028,47197,63469,49222,53075,25359,89725,69958,91779,75860,58495,76747,57471,14341,74017,14482,50756,19326,60942,5755,72154,61525,10515,96038,11926,37236,7118,80850,99469,26222,35652,16868,94839,40808,44417,15870,969,33916,52140,43518,42046,9171,69316,25599,10552,61725,92589,37633,15995,30909,32373,2807,70029,10740,71360,66477,2721,81679,86159,49166,89627,69575,30210,60069,93101,15032,66947,526,35485,22415,82984,16301,8927,56610,77625,594,49131,37035,38366,44821,55929,31671,49000,221,57087,87574,80862,47337,21474,95626,8723,94899,82359,95429,1086,59977,80290,463,65633,55058,42833,74088,84433,37089,22239,26284,96242,9985,60870,65435,15746,23764,40970,27629,97293,49890,64868,65058,9809,53706,13975,87439,43612,48059,16843,63426,81472,5694,39396,28804,18613,36289,41696,99474,39946,78915,89221,63342,4036,51645,92172,16807,40296,73641,61270,70482,65180,67820,11983,91666,21600,23059,50782,91706,47081,78620,1575,66827,78999,86743,95824,39425,74774,64327,55932,96015,53243,70818,29332,3818,32287,84061,36412,97693,81298,35331,14800,42535,24742,94737,49263,43385,58917,42484,67670,81896,92649,95182,29258,84230,71311,12306,56863,43477,64340,35742,82527,64403,9564,1444,60417,48197,9703,8691,79554,79065,5893,50398,80069,91736,56919,23515,69394,13998,97319,7681,95713,24528,67021,62030,57307,36417,58533,88696,90107,2633,3240,80609,37320,70529,37140,69602,99172,38770,72746,35469,95652,65917,24793,72149,7412,52839,88501,38966,20271,97952,2129,1230,73345,25312,79362,27673,36837,92283,20829,30779,30451,63837,67441,65351,65554,70400,66630,83394,18730,91982,82868,87030,62893,91711,35273,90769,96087,35195,63617,94831,36051,55403,60937,5824,14214,61994,40775,68975,34319,71786,6190,70217,80333,42811,66857,59003,61802,36723,40546,37157,81106,50931,25018,11287,33159,12014,49968,42088,46693,21803,45839,7706,57662,85516,30545,80984,43212,83892,17730,82181,76400,20312,76384,30581,1476,79673,4461,73845,44375,66541,78654,24697,98648,42041,31607,65675,32953,71081,23393,12333,41884,47957,38568,59496,34581,99995,55579,41955,74997,11361,5374,68859,15518,5255,7407,1004,2851,7789,43281,3907,776,10641,68329,22044,2618,26207,53370,81305,5349,94735,16456,6459,32542,91353,80624,52726,36600,36583,16892,26633,90923,54213,54406,87648,96605,48934,56073,2767,19627,28095,6188,25935,72120,4374,69397,6986,91083,77262,6906,29545,63153,6613,26551,23040,35797,4420,43748,76603,15026,77340,48607,41919,83448,68408,87352,48027,53238,4185,60179,38819,71678,70439,69239,64109,538,17317,25909,98642,92332,74286,72881,75423,36078,23114,41484,96007,4710,8064,88335,73865,30158,96669,7096,74629,63846,92339,1871,49657,89951,54021,64618,9819,17723,91789,82408,60234,58436,26977,24102,52481,63920,75036,91164,94085,46210,49926,42816,39220,83802,12394,54125,31757,99064,49029,61611,40903,89621,16575,17421,5443,3813,74877,93265,25385,63492,39984,29342,18278,51884,39659,19119,49814,15249,71175,44481,12792,20161,27939,5148,6353,94804,71025,24623,52750,16167,81050,9905,23359,41169,64272,94404,22871,88989,61933,76961,40893,33302,52991,91105,42571,43434,31237,33370,80151,41885,44144,75393,43621,8185,88993,67209,85610,47742,22960,16080,5605,98959,57223,96098,95625,93836,14508,13056,48897,44514,50822,87486,69477,43783,21790,90138,89526,34189,75143,19488,73429,86403,22237,98108,24996,33557,19947,77618,17746,52468,28217,22783,58900,18568,84492,99,56598,54010,66640,72467,75541,64187,79878,9535,15521,57911,38518,22496,39586,36174,74108,25814,83604,24451,49531,34958,87176,82598,73715,10995,87147,75727,51252,99597,78759,32609,86212,11627,45376,8828,5593,35319,98668,20524,89280,71304,70839,82928,45697,63330,4205,16527,95303,14258,63386,55872,60914,91205,38356,24496,53543,47604,1338,97780,45270,66143,97853,57663,67465,47638,69001,7217,63292,21920,15131,28634,96035,62592,84901,91144,36939,41687,70858,81971,18488,60398,51551,86475,79245,58825,10066,74715,34649,96583,81357,21494,25075,16447,79930,63158,79369,67297,87890,85232,27856,39723,91812,1131,4157,27376,56454,87712,90941,84839,2827,71991,96719,30802,61932,58457,3673,6396,15110,18914,6166,74279,29105,828,43350,68922,78379,74512,56093,39205,95164,77389,11889,29071,11113,73118,77855,74352,99351,19601,52022,38940,13993,91860,62715,84473,53883,10679,20204,94942,88220,15657,25564,35524,11998,41073,20741,563,76386,72346,75102,4923,85644,96512,67103,92128,5539,70727,69741,99302,55998,16970,90242,45905,42126,69306,87336,45245,62440,74326,45855,26138,6905,27597,91184,33029,32253,70578,57963,12157,16581,53545,2836,65719,97960,24146,35679,13176,74029,99439,64046,11441,15247,66915,1166,8874,49250,11477,15454,41061,15309,63641,25941,37561,41640,352,6141,30282,15909,20844,69792,59245,63843,4707,72688,93348,16556,33875,73156,55739,42497,48992,82757,32193,80384,12591,11742,63336,58423,71355,14970,55229,50324,38220,85426,43807,12555,79733,97569,26817,4714,23603,45840,33664,82086,50488,69346,67863,94992,20087,80076,26206,26946,89964,75261,36325,54437,1147,41811,83457,70796,30767,40838,35622,63915,14123,61415,61348,3384,77822,15333,80257,2820,25233,99201,44281,78198,65441,79671,77677,73285,63407,96470,79583,76934,16281,73001,51288,48853,24270,90522,77334,89271,4153,40803,14972,81274,79305,58358,45641,62634,56694,25321,9532,61809,27872,24995,86295,5862,93762,21195,3171,10009,11025,30175,78122,41571,10042,70704,31378,26711,18687,50588,17687,99014,56739,62413,19318,87914,74623,95455,86450,72070,95426,40500,24083,32212,90567,5160,89391,20255,7171,91488,39051,66950,79563,8015,39862,80843,72963,69568,33718,83167,29733,33672,25479,11115,53537,14787,47776,85167,4848,57326,71461,57373,20339,2920,12862,34076,40426,55819,84140,95757,95794,26142,94556,89647,55774,84650,69699,7046,416,39242,71065,93422,47093,77460,45600,65684,22432,30622,7746,44014,22294,20852,92272,63004,54114,50356,14729,34411,92209,95998,87580,9030,91787,29798,33622,72407,37746,68700,67424,64155,34633,23804,53797,86918,1257,45121,5717,10230,2523,19067,34520,13887,541,94189,27644,93617,61513,18598,73016,33587,7948,41757,91733,81433,19554,69627,62583,61701,31675,42044,54899,59711,71323,35824,58352,86366,19403,90778,19736,78129,37340,86870,20833,52672,28877,89822,66865,41038,15017,81590,64802,15308,2211,19714,39316,34284,23085,62061,8722,17321,73567,76086,53630,67776,42400,47922,89338,75408,33992,91692,46716,10423,99984,23478,49272,70792,15971,87880,17966,37205,61073,54540,11543,72003,34027,67009,97008,6863,97423,86160,1629,90583,71174,72093,7401,6896,55845,77579,71100,20356,54731,14432,4595,64399,46006,42363,78336,50224,51633,55605,76956,41735,31601,68103,52718,79616,69774,97124,79416,21953,60044,36743,83369,71067,70268,72820,79619,93621,50967,46203,92201,78085,42268,56393,32937,89179,37008,45924,97020,96580,40324,61414,44028,12828,32234,80790,3254,36527,690,2170,8508,64806,78778,9714,93080,71359,60273,21380,37376,55170,91948,6933,59295,18947,34798,78063,89117,50592,70986,67089,69912,93962,38188,38071,9925,69840,17373,6132,94506,35735,47091,61635,87306,97627,22993,77632,91136,7140,96325,11311,26929,84888,93605,44916,47744,6703,21005,47289,25262,42467,74735,92720,96733,58173,62370,22445,94699,45673,83134,73203,89045,69750,88564,16507,87328,99174,39711,70175,57851,69649,78562,72,25416,1132,92135,91935,73139,9549,38563,42913,80298,42087,89640,9702,66446,5109,9821,29350,70117,82734,80873,37610,62520,67880,98068,40194,13665,36485,50326,31530,22213,68371,39240,63413,35809,2190,18773,54992,92043,70049,38997,13059,97052,40367,90553,15320,63438,73600,83489,22487,92895,51717,46043,7511,67316,51599,71017,61851,26446,5763,76260,47531,89077,67273,81726,34368,47309,67264,97355,88432,65381,43111,51225,90898,92505,18484,1394,21813,14242,35926,11569,20012,1618,23236,20691,83523,98837,25338,51113,18235,64916,98564,910,57899,1415,27956,23009,51231,19503,53784,76607,3844,43122,28391,56414,28386,88289,18511,41448,17956,15560,25609,70323,8752,39579,52717,90877,28304,67922,53402,71387,45925,81940,50487,61934,87243,4234,75092,14983,63565,36721,20500,81015,57925,32853,97591,44765,64869,21903,77654,4970,46703,7145,27033,21882,7329,1639,69480,6683,92668,30573,737,78043,28836,13535,57002,48163,13735,50040,7830,23333,27732,13615,43038,69976,47163,43280,6147,76365,16075,36659,66744,24362,51043,66840,30072,24565,96578,59383,27264,41656,11023,16012,59015,97522,7612,46099,1566,60224,13035,93150,69491,31382,82050,54339,63850,69531,80095,25967,46395,71439,52829,70299,67225,60495,25630,96102,74457,29959,52825,58032,56145,54150,93296,31261,30606,47491,17036,68687,74262,47085,37619,13466,59763,24253,56378,11854,74075,68858,42514,65038,95253,39651,51792,59607,54421,74878,73218,84277,56712,13018,56999,68914,52797,93692,88199,48990,69870,56498,22042,77636,3573,68192,57700,14068,36491,56537,78792,94002,35750,27906,72292,331,67691,65598,84656,85814,35327,95162,67128,24007,78383,40617,53185,3859,24540,64090,81036,51347,11864,36727,82545,86329,91310,87911,21309,31708,58098,97205,69965,60454,10272,9000,14479,56221,49597,41793,92765,19524,25589,79010,39710,35018,75459,91068,92992,23390,76329,81503,79338,14776,59922,28460,86170,88868,75809,20492,57478,79242,1343,18846,7784,26974,47225,38525,30225,72169,74104,68411,38364,33026,47470,18935,18308,11370,90947,28545,44242,1957,47748,31816,75303,20675,48996,62234,24454,69855,12407,82839,73267,67473,51689,19319,79549,51268,41346,54307,36866,14933,35301,6673,71776,12002,70998,9764,10266,95093,69717,83243,16416,4166,62942,30874,50977,96684,34564,99652,45843,96049,26433,58884,20099,8046,802,52078,8167,36137,28862,45113,95350,46711,23834,55402,86204,35177,81335,40164,72578,48281,84156,77207,50266,97432,34854,59172,66372,43860,3502,26477,16161,43731,36414,11376,96389,38710,58669,69679,43682,1633,44993,51932,97408,76764,41089,52390,60183,58927,38394,60754,12950,61371,10986,75832,25224,29022,63743,65518,21752,66168,54316,91751,68851,64166,60026,67000,48749,37614,73160,57046,26663,69639,8748,17770,1991,38484,5841,84968,59911,5181,13593,24074,18642,89874,10363,51395,6291,59663,57803,36927,60027,89459,95132,25881,10206,71892,13636,99088,23221,79466,91059,14633,11661,26083,97476,53039,89395,31388,26943,59608,69436,17875,39903,13969,2174,69812,17139,41703,37318,88083,76540,92793,32302,19493,78026,62482,52871,14518,86815,80227,32405,92684,9559,60042,16903,95213,4591,22941,63620,36066,46068,11092,34860,81902,93922,11008,21250,88347,60790,35302,93389,45618,81435,88366,80708,87012,12182,69670,57487,34534,41495,64153,53072,89727,10327,4875,11616,79834,1773,50517,15152,47970,37974,26695,41939,36534,8778,87010,68959,20557,90157,21019,79852,84181,53168,24618,32676,63354,95531,42930,89217,80971,42270,60963,19061,53015,54589,37138,11314,93288,66345,56193,39562,96152,9417,82292,27340,80044,36711,5655,66981,56339,80917,53679,75290,35391,9080,16043,77819,44194,41233,19514,94362,52174,87730,21755,3192,89519,12712,22285,73469,68242,24465,44476,75317,37566,62566,30551,57980,71139,16840,78774,9788,53891,31700,94848,84215,11690,35231,68410,22699,64108,28608,17516,90664,36662,84112,65853,29704,34516,82582,39971,99035,75515,99146,59356,22686,43214,91798,42242,75283,28599,9268,31326,65809,46577,21022,10743,82986,89510,25030,44600,31527,41029,53460,49552,20122,44106,40486,62473,81857,95193,46781,55213,20780,64132,7048,33491,37434,30241,39179,77982,66898,98150,39270,1866,58181,67422,24170,89726,94271,34409,89509,13119,66084,94734,3641,40270,19639,83639,34541,11274,11997,86386,76091,25443,67181,76344,30135,69078,40347,40905,7748,9102,97546,55956,16608,92550,21160,45323,7850,28244,28641,12432,70984,67304,65389,66318,48465,42364,97339,34919,86277,16641,89284,91716,37555,69173,10516,6549,61059,17544,55994,69966,81188,24947,36998,21382,44172,13954,37251,55434,17738,88222,19656,60751,50291,75671,33071,84944,53622,31177,83973,2351,47510,93066,31318,2491,24677,13504,73635,32259,76551,68287,73359,80084,88676,12515,37602,32203,14070,14353,92801,71073,25644,91502,3375,46540,51695,49752,63293,27635,81961,88483,24537,93831,43300,7785,725,74647,25400,55982,41499,88224,44435,67032,5161,39637,65720,37451,18177,59377,66824,89203,4466,43078,68101,22910,73231,88451,93025,62179,28635,3582,26632,10435,55485,71299,87426,57679,530,80903,3648,64165,13757,76878,91082,98954,55448,61382,69875,41506,31784,14127,87143,4325,47348,21728,33735,53854,70500,68429,54525,12173,99840,28359,10713,77013,21712,32348,91754,86753,87474,90001,18904,17070,68560,89418,73087,94672,35634,92760,73088,84422,74064,35427,5055,26561,46276,66742,96390,37784,22030,51677,46563,3418,48926,72176,51432,84081,10851,16692,98355,43954,29869,68752,68613,40915,1932,67587,12060,16359,84301,4995,65258,55814,20922,40972,79075,59826,80241,70127,71943,73475,70430,99669,26998,77821,29160,43546,92486,75600,66946,42548,42035,37419,18805,54664,63761,51919,51721,8121,59965,76571,6283,25169,19465,81564,68201,9643,85528,21221,43396,12885,78234,74147,88754,15464,8924,98220,4505,37311,18460,30849,82555,21243,49414,32396,52837,48737,65874,50743,80104,90601,62077,63328,391,60181,27967,59928,71367,39176,18840,45903,70517,93007,30915,73623,28161,27306,52826,46893,59598,85233,9826,96872,91942,2327,91984,13187,5304,92189,35857,1553,48642,9923,3774,39678,84412,2328,32446,68362,34735,78880,81025,24598,70014,549,74680,44926,79064,57219,73605,22918,31940,18190,8774,6736,37776,36778,4733,93932,99118,63203,50629,74529,44772,12727,31684,24770,28769,97509,94021,42379,19176,25302,27991,64564,265,69858,52644,84584,65158,42891,21627,32260,16498,39702,94265,65115,64011,36651,3509,99959,66081,93271,43312,21451,5060,79006,46932,69488,18441,50208,90080,33987,50238,69817,36307,99841,8908,32783,3983,72709,21333,50245,43756,34831,31090,33332,9679,33348,60542,37467,20054,22092,98591,78702,34295,48635,52434,25133,47881,67593,73723,89236,97583,15925,2113,63054,37537,42671,78594,32392,90188,59524,87661,84076,59625,84828,71601,45976,26866,50347,16804,96786,96554,23989,64159,57680,94216,86104,69755,80845,73923,19844,74558,62044,48509,68774,35217,80678,17732,8407,32598,83730,25386,58618,98065,5059,97574,54712,19540,23591,44607,54633,96646,62398,82751,88616,68256,54434,64960,62925,46682,50585,41211,74966,13379,6090,85707,52843,62008,90295,67640,35184,15200,28186,82611,10154,88973,13753,63365,10735,64112,33965,91717,22353,47783,51369,1819,24079,85588,19615,77243,33173,77893,29664,94377,34272,73983,69802,85303,40777,41691,38689,92009,14136,43425,43540,58232,33851,99949,56357,38051,4191,39006,27696,11800,62302,66833,28999,69426,61162,75826,80870,84851,63154,46594,14699,68463,88444,14607,56449,54698,27113,20387,6923,56511,32636,39806,50204,40140,93295,79960,77782,16334,28015,49954,39295,12350,21933,73670,50400,61428,89862,79841,34045,62749,69549,28129,95825,19038,59611,74035,43786,55070,25918,69175,34567,53701,753,77227,69141,33287,89499,81225,74991,53267,96994,13679,87708,68846,54983,35823,35266,19013,45374,29801,69899,64381,58767,383,74866,72060,21878,49443,57084,218,3234,4814,86810,64119,88288,41743,88238,43759,48935,49160,61330,20224,86915,41799,82340,26484,30822,69646,99585,35478,65848,7648,75273,3508,64374,15689,73813,81509,1751,32923,52569,99447,22731,25728,86054,71472,64940,13742,44098,24173,66810,88198,52710,38609,96848,90213,86804,33695,15166,99562,42223,26410,56213,87453,19548,81253,80380,87240,72612,55667,37359,34985,74506,36860,12479,473,82217,54163,89477,53997,24278,10121,29472,48921,91162,91565,55240,90446,41864,68924,79543,96487,78320,78902,49878,97315,25350,79879,47006,1095,49129,23910,38224,72428,72054,97659,95347,36032,59281,34002,56469,43511,90936,11232,72436,77831,9713,52909,47202,301,6115,57194,12920,96799,4320,98615,97049,18124,6018,67727,8686,53940,93586,8117,5764,94541,97454,4222,24061,66972,20113,25761,95142,45907,10619,38201,59248,10921,62878,38341,59095,14222,10403,38830,7232,95830,99525,24768,6709,29185,65419,24097,26863,24152,9626,26938,83401,87895,15789,84560,23970,17996,59725,77581,25887,89031,78963,40217,18437,89145,15483,67547,91221,82946,51448,6555,18829,70553,87553,47267,64281,29,64774,66149,28169,81837,11921,24298,60930,37396,75289,44497,56376,23422,33634,36142,40933,36850,97068,16821,90396,25379,51844,33266,38050,6532,91630,80396,65680,48244,36397,82431,92216,640,21253,88201,67379,14582,66841,82893,43029,16214,95223,7411,60940,8037,57175,33351,54915,58429,60058,42967,83887,29195,30348,78417,3051,82993,50866,58277,54566,91303,56253,81380,94075,52294,1020,12290,64433,54578,36884,15578,11443,27239,66380,4437,96380,25688,13779,91869,68709,24495,63101,61977,15129,30629,80053,81168,6663,78810,35691,83287,41459,78874,28827,17690,20077,51902,96805,19962,68668,50564,21814,31797,40954,93406,41400,63340,14560,21891,89069,7809,88260,37521,18379,76885,36720,79540,19991,56304,43297,93154,39822,85665,13353,91480,79628,30004,36205,7254,36599,57532,31547,55204,1059,27998,19933,14234,26157,75765,6888,91646,56595,21628,96716,85844,27463,92891,80702,11936,39964,54221,64307,66788,51247,14600,35448,19210,42862,74190,24052,37519,12323,46935,43095,4645,55077,30271,73895,30753,30942,28895,51559,69114,78074,74025,64514,88912,72641,31571,30274,44081,49212,31630,8790,65179,1745,46018,1556,48420,90686,93112,33956,91071,45722,89089,55109,5776,33073,86558,79461,70235,39204,19959,96322,78803,77768,47607,10433,37880,82078,7544,43096,65880,24554,61541,65318,84295,72808,7591,39988,54928,27006,38937,92939,59933,78061,23857,97046,88824,51303,22809,17523,50988,51081,11355,63042,48332,36715,25580,96897,5145,46090,62880,28241,29250,42526,41049,76168,41392,18205,45201,62346,21478,20949,87809,31361,13354,62568,84739,59999,44515,57508,70620,21726,8171,4484,51648,43879,46886,78342,91591,9926,29255,80888,16024,29276,2334,88745,33427,92702,25397,71543,84906,6632,90654,87200,33376,56379,9399,27291,97804,56061,35010,38158,85912,6692,54758,85963,86904,36804,57559,5826,55608,63392,73368,19683,1399,39101,83775,11941,28443,30970,30933,22903,36204,42714,94797,78477,11996,81257,5321,61192,107,55143,63117,93588,26644,15051,21091,55421,86066,10071,25059,78794,5099,95483,34100,85448,76738,5203,585,82853,90813,12839,43834,61591,94209,61793,99674,94880,2792,47909,42686,41569,80264,77011,91810,87770,22032,67567,82254,52643,59696,35556,47476,53486,68034,7169,88365,12015,40073,94827,90461,44445,66343,74383,53732,20518,71952,63859,889,20688,1430,48477,34216,78201,78721,34243,68901,16073,18338,58899,15008,58368,23048,26413,87112,49577,54022,42800,70504,34285,42407,90968,25102,7421,23371,29663,13736,76271,12099,3750,10771,26678,11513,1869,4319,74479,76155,8542,90247,86771,20811,76886,95246,15919,22286,74829,16649,48469,72038,1850,44747,17904,81518,85609,35732,14533,81694,5558,16637,76451,4414,7309,5038,31207,20005,29299,10658,42553,30771,35281,38287,34614,98806,98024,83822,46297,15010,29090,67989,20154,63642,71199,2315,60657,46843,70332,22420,76210,77125,58209,83849,90803,64566,43060,55445,19648,80901,47180,88703,17726,59493,99735,84958,33679,68388,65239,14004,52492,316,18741,67092,37090,45604,77843,92187,75109,28792,90282,16486,91330,55711,49431,21733,70236,75753,68523,51283,19363,69849,15880,27416,16582,34801,96743,20873,91538,71191,27860,8059,40512,53213,3341,46909,51349,93795,46327,51748,94059,64650,69903,32775,81473,83869,19348,67919,14430,5370,65943,48359,43969,93900,61819,99187,83544,28068,26145,85084,330,18187,909,43826,47600,78448,86211,64768,16067,69584,82612,46064,58539,95923,51201,71919,65757,17493,55446,87191,8690,77303,79321,63454,82331,74635,13819,31942,67095,19026,96682,98793,28886,23991,55496,1068,29224,86233,76834,51912,86835,30326,19831,65474,98786,30365,64331,67513,69533,59578,105,78744,12625,13227,29029,69601,59833,52867,4981,28036,36479,56985,68674,24921,55644,15270,14040,37536,58166,59486,47681,99376,88076,97242,30569,72165,19986,62086,34159,2644,12651,25247,97562,78584,17214,56206,87399,55480,93547,37219,69371,74199,41868,58206,70098,48198,32999,37406,79074,97197,3151,47304,14286,4026,4793,49054,25389,14476,28889,73123,97073,5106,38577,74013,52429,14621,21379,16268,7007,5007,72986,1744,17754,99001,22762,72997,9243,411,75165,17046,14235,56611,33060,40598,66722,56335,88031,75080,3414,19876,32457,57425,16234,4850,48421,38048,79949,76408,61452,58556,89776,5091,62750,52297,10417,75160,92260,85631,76914,83772,18421,45484,59547,51512,60796,22800,80653,55392,78301,64501,15138,50856,94902,19268,38534,48178,91150,82241,68675,22856,82834,96653,30482,70017,61743,57969,18390,57966,31424,80892,22443,70691,18286,63702,61707,12620,97067,40927,40440,90750,94642,55606,79347,73441,52601,86665,12593,7893,75507,65547,94977,8266,29916,67074,367,89118,48202,77070,93038,44250,68273,25249,46428,6700,72210,38295,4085,73207,95738,74695,2488,67376,55004,13992,45230,48008,94438,2,86602,2163,45339,57863,79224,9479,462,78221,55425,11275,95927,2616,45562,58411,10902,97532,25024,12520,74806,41832,35220,135,35315,21054,91095,64214,18,30145,90093,33120,25112,75201,56894,42207,11036,44393,67785,14079,38069,92161,36495,23039,84282,22223,76405,40712,51025,58092,66337,63356,11460,9116,57634,29024,63742,5519,48250,3776,33930,80228,36373,86300,37988,71777,24407,61638,62132,26629,82022,81562,37949,64273,52641,40672,53430,23606,3855,26311,75820,54584,23477,27049,52,81363,74542,18345,39504,45415,13526,10471,33030,86913,59143,33826,31860,70246,88368,28322,83502,28226,239,98953,59458,25467,76531,45029,6075,67894,4870,1247,99572,76106,11034,96829,29284,19049,26357,77081,78807,51852,74426,3446,77120,44665,3549,46482,42892,8500,39123,86237,89806,5714,91999,15059,20901,86353,34509,62574,69429,1568,6122,68080,40077,47190,81490,66128,32261,21218,86014,17948,77401,85234,35158,30476,21060,70028,88678,36165,90217,65753,31437,67417,32879,56101,12621,64659,98516,18347,97947,35190,84587,87077,5633,3784,57429,11973,41724,16981,34597,92386,429,47177,35962,17534,7459,19911,54299,75038,54305,58276,64100,47884,97789,30601,43509,65667,71955,29502,30948,13689,42926,64068,41059,93246,98109,32353,28133,97474,97858,78535,50971,23448,99279,77646,6140,46834,64178,62923,48854,82030,75052,86494,88625,17219,86517,8775,42165,18411,93059,49913,83710,39875,79524,41677,76968,78209,24305,35860,84440,59979,94641,13155,60642,55394,31884,6835,21513,89078,63313,86307,8362,98522,24225,74439,667,78685,10635,7920,71651,11686,44717,76242,51121,19586,17622,54166,44978,18412,59499,72712,70660,58467,9335,33375,39088,96790,42874,62078,39889,68646,62129,48253,70737,14535,69094,66130,62121,28857,30806,99901,15033,82958,97946,68777,15908,77024,9548,28617,47296,53582,94129,18501,93581,72128,17353,76280,31581,1664,39216,46567,54607,81591,80131,59488,89430,79925,22771,41636,50671,8766,70951,60000,2212,73108,72028,4312,30459,40640,32940,56396,11901,34115,42550,15392,89970,66485,42021,52137,51619,44548,13460,54986,87402,97613,37032,12735,49821,52794,47546,42979,39556,74490,39573,16360,84777,21360,12457,51088,53733,86162,57164,47753,8149,92714,91380,99369,51631,68733,12304,94999,44565,88338,14511,62671,80871,77118,67375,94294,59332,93815,87990,30929,9758,89381,41648,61286,484,92133,21509,98711,73031,42702,72747,326,93750,11529,20285,72174,72571,96044,70914,5256,22043,33584,94424,34507,76158,45049,82373,59128,60285,95005,32088,73748,93629,78150,93315,34263,66919,15214,98232,28785,76357,28572,66067,67252,35282,21210,57264,50021,49405,1769,71734,21652,99314,7631,59758,82988,36366,51001,85013,94022,55026,2674,5001,44930,81571,10513,15176,88699,5680,93695,81132,95694,4379,48045,39107,26826,39004,58717,36212,2433,84510,78791,400,12652,5232,99611,50649,63105,57707,93799,45890,17030,608,77124,20465,51405,75519,40964,23945,19112,83582,14987,96089,88491,599,31912,69110,77692,42188,83517,21103,68480,40050,45151,34088,60146,74689,51041,40852,77505,28834,91614,46690,93013,26836,20020,11761,69508,35818,75072,16773,75106,63856,27651,92910,91308,61926,45994,40805,58814,81813,57257,97655,43763,19277,15780,30350,40020,31268,54498,94286,53870,31758,40413,78857,10672,70148,42045,66997,70571,77392,6520,57523,23595,42459,31595,9209,13275,44921,89502,94211,30294,36689,8611,58557,20881,61972,42387,87918,40438,38892,9010,30429,60372,50391,39981,96332,98406,85030,33865,33860,75508,66575,88929,18381,58714,48957,65315,43662,72433,74235,9594,83733,11561,25627,65496,15329,41264,27319,63378,37773,19322,18119,62663,72925,76609,28056,27904,37685,91626,56890,55355,83472,52476,90919,59691,46604,92534,4250,88393,77521,24615,83638,36759,98074,17940,36468,1069,25883,85042,64639,9952,77204,71236,26792,46321,71348,58628,69758,39201,54321,10796,77775,20024,5818,621,64740,94042,49546,45044,91337,47115,91618,71662,24630,19603,79532,86901,80051,63379,45602,59449,53107,94062,4869,24763,468,27014,75909,82579,29207,37384,82571,35505,92229,11265,15986,12521,89894,33891,15796,13717,40814,83667,70342,42740,28652,77169,99728,22658,75282,81466,40331,39445,48220,75117,66503,55576,73879,115,50076,27488,66988,6055,39320,41960,31405,51158,51219,47996,74692,34222,52033,66620,97098,50500,48073,39769,93355,13557,68183,62996,70514,87286,27642,89877,30530,9655,43774,26035,44894,51608,10138,56640,19452,85762,48659,1314,67176,55046,10937,53230,76935,39615,20034,35921,35489,53428,83131,50717,28040,44626,80164,38668,59662,23923,35067,90420,18092,24214,24971,25116,19682,98434,2900,49169,82076,41104,81849,15332,87729,61582,52729,7940,73420,60114,1559,82509,44858,68446,15714,94625,3765,15852,24442,32922,27617,34601,92169,56867,22394,74537,37906,77703,20108,69767,43658,93982,94060,94408,5225,6988,16316,90308,57664,88623,24687,11994,84617,22842,189,39158,3434,53177,29522,54598,89539,40191,22955,29672,73474,73408,17019,37836,57411,96303,21872,65388,93434,3737,89064,36733,95141,48625,15479,4048,68178,87704,39541,67635,43162,89723,52227,15079,1458,4195,20038,83963,12082,98788,18814,88059,72607,78008,46961,67224,46885,30585,41201,50163,38968,45269,26981,41932,62857,85456,17470,54414,84990,77414,55524,20947,47547,28997,15364,53464,46277,52099,18679,19896,13333,69017,90341,19746,98528,17798,69901,29698,23472,51302,46190,81028,87773,33291,4253,87525,81622,42626,8745,48633,91115,46989,28380,20667,49651,93129,9430,49850,45882,70816,76393,66847,92951,93443,73815,33198,41532,19405,69336,8433,94311,22588,83048,62565,17122,71880,76002,84969,96058,45412,31655,40468,6719,31443,5213,66036,5630,8168,28442,72162,67784,8320,33659,51408,92148,10565,17324,52320,5895,44408,19024,38760,86473,11613,7464,15724,88690,59408,19153,97156,11493,91998,37039,51871,36953,72632,39733,97413,42306,53860,95060,90154,10,64471,34277,2203,7930,51188,75161,70394,49119,26364,84383,17226,86519,30631,31867,84670,66044,7176,33668,59571,1979,76425,5644,36587,20045,70628,37815,49895,87905,98614,11365,25885,90566,13531,74660,17109,79666,8408,42456,52696,58442,65842,99472,57267,26643,27356,97343,15784,25399,29364,5650,89115,6578,66952,12522,87091,16933,13825,29760,51832,7150,91304,99603,44083,4413,71486,67619,39835,30078,57947,71301,5103,71196,37981,57413,98923,42886,36000,93890,90973,67728,4922,97329,17735,79436,25041,95195,99315,40415,42249,71520,60327,27947,2992,88241,18210,45187,62865,85574,70256,38858,19501,32224,63892,87068,98592,72585,41060,7914,81343,96769,90791,51938,92834,50652,14312,30034,71320,79043,23658,85376,95938,65307,21488,3101,9185,56306,17891,62202,77473,52447,14630,15354,73164,36994,81812,47314,62343,36429,38636,67393,42001,80148,31573,11630,68230,37062,51756,96987,24500,90376,14099,35068,46547,52047,42475,25647,54371,50839,3934,7285,67204,66609,43074,79656,93289,61820,53871,10354,59740,78683,94953,12623,31433,59239,74793,92163,73090,93475,36090,80213,7766,7059,4346,96947,79845,65870,27282,76331,11269,21285,59410,94245,34067,74409,86048,58297,32210,81258,8487,35725,79128,86472,41855,53867,60743,56284,78832,12336,70558,64181,50059,56265,22121,23415,74577,38635,60323,57055,75079,71515,41135,20889,17572,56549,15367,16953,37303,44369,40354,91951,14877,26801,36105,57301,8951,60359,60939,78397,76295,2697,63474,20257,12096,68456,25863,79445,86751,8395,35577,56286,56784,20878,71558,49873,32347,35378,65077,2155,40526,32336,60529,81158,47150,38873,83372,25943,31140,86809,57195,61924,64382,15262,86885,25874,48534,98756,80513,30812,98850,33983,15715,64139,84083,69497,88628,67802,30472,85888,58213,26203,52684,85965,38452,46118,77171,86365,74451,61551,26538,70981,77609,66492,64203,68797,77313,60755,26849,27811,56685,8679,27805,1259,49012,34471,97786,48678,14285,38630,15642,92877,71628,64143,19265,72424,8303,28444,66905,43522,78229,30028,74163,48079,47256,65821,20958,94852,25633,47929,1286,78237,53008,31995,81667,74127,35293,73804,44690,92107,48610,14783,52032,70580,83718,44788,687,15775,70010,43529,73749,13191,27839,86738,86479,87279,41728,60274,55669,76396,31185,1398,48535,94489,81625,2793,61280,54527,83954,53426,79515,11653,68441,45699,84415,72035,4349,81894,98225,51174,61450,73141,80863,66924,47619,85714,26911,15345,85783,66047,24657,91404,33781,45165,50733,27491,98112,95414,25289,38650,85929,56530,44590,62775,93420,16855,98027,3407,46673,57074,10127,43415,88029,78928,42384,71611,62216,95,33593,2638,6561,9756,76225,7638,13925,7549,96275,29394,66893,14883,89729,25381,24927,90944,43145,12378,15924,28392,62499,38722,90366,381,39437,79764,6095,88650,64551,12780,43246,21731,74474,9233,67003,12914,28619,25445,21603,96454,80671,89890,98129,72465,8221,24542,19505,44678,22777,65176,31603,79865,51378,76902,55969,57054,17905,28847,83898,22512,57419,81998,74889,40729,88667,68161,40059,82903,86406,39811,26879,28215,41987,816,56257,65358,74425,93325,69189,39680,73051,39111,56908,37322,57752,3065,98207,22687,83605,99328,44722,21356,37939,30703,35495,34982,41563,26212,22075,7456,88999,42595,66639,19350,77384,89382,89955,54812,92595,75350,85531,93510,76261,58482,1266,80536,62758,53360,30679,25576,20876,55175,91189,66881,23482,24967,61221,250,64530,92613,48177,98466,67123,29412,64785,14881,38868,8667,54882,313,4247,39966,93302,97681,53056,37824,76691,92018,6993,28130,50606,48403,86167,68611,83242,41475,83458,33652,20558,22712,92317,52449,84452,23546,29626,28054,24698,12675,32382,44987,87886,43045,88235,34803,98410,18391,43534,86689,5906,19387,8461,98478,22664,35224,66708,82640,89929,19158,12245,40148,38247,6193,36554,31900,94365,36889,836,8415,28839,45963,37721,67216,84071,55076,25022,6595,66977,8156,34012,54590,31099,61891,29132,93559,82055,26612,43665,48325,48906,31450,37727,16687,77981,88663,27182,15050,77895,58513,26126,61458,60894,91683,10911,75368,43245,84543,50249,31131,83463,34786,92057,69603,7578,25288,17877,65299,41580,79525,2580,42333,71321,55467,69648,16310,92830,35216,80030,13233,75396,56800,52711,28027,73181,18171,35616,77764,50338,69540,77047,54585,23567,103,20248,33646,56792,323,50587,14858,20522,76443,56290,59950,97467,50434,84621,61666,8797,20642,51138,62952,85440,28340,5692,54727,78182,88297,72046,27026,4479,71214,16177,46296,69076,89565,12040,60254,57296,42014,55619,13243,78296,83844,1454,81404,56942,53193,61213,44197,60957,19189,13434,38165,53684,438,94098,83383,6909,98558,18746,70597,68622,83992,57576,43521,67570,2602,12706,75443,27535,99609,75949,93825,53251,40740,58216,18450,19057,52586,53517,38263,61768,69057,81508,77325,58435,37137,58114,53118,50044,28007,55800,4324,93950,59405,66387,66489,58094,21100,72497,19610,28389,3459,18454,73291,51572,73677,40974,59682,80732,33709,403,56682,22347,95272,8712,57580,65807,45137,17050,95788,64415,85082,76854,10019,44203,28403,43180,21492,74113,82808,3595,70164,72609,44893,53538,17831,87529,51315,7030,3206,37764,60318,50827,7844,89787,17170,45628,57954,98045,44458,19670,56614,49245,61410,28856,63564,74904,99332,34825,31880,46645,30820,50310,22585,3823,57722,30347,13254,58517,43728,31701,97763,97801,10593,89,26740,89937,49095,83413,68260,49613,83303,37724,43940,50404,69485,12613,87819,34625,53781,64387,82175,65969,69816,12319,37532,52660,41360,10978,49585,6463,84425,70640,99032,99744,15254,87851,70188,80265,7274,49964,81279,72333,42230,39210,66886,45330,74657,53863,24871,51065,48718,91607,11089,16550,14426,11499,4887,43979,45080,51651,94275,11719,53606,84763,60095,28075,10065,93224,26705,86866,32471,99343,3887,25099,99983,19936,59345,95565,78287,15453,11567,11340,19740,93352,61858,45897,72082,75681,72687,28654,7341,14820,43506,85728,20498,63531,18528,21001,95812,66055,63432,53448,4741,80991,23107,4448,30912,44703,7372,99878,41109,42782,17267,99864,46959,14494,71736,5111,68992,3570,43646,72016,62959,14766,97515,79860,973,4691,86593,57125,92822,71871,71580,71796,76290,39510,49981,99764,68367,67340,42859,18616,17676,47100,76651,47856,88320,31471,66269,69148,45471,43934,50927,85732,1146,1663,24394,56336,50920,66315,54071,32881,9806,20622,6217,78087,58497,80072,26237,69763,2877,78771,21204,29023,98037,34016,96231,91559,24655,83859,99570,39570,4800,29117,85737,3575,74382,34740,31243,57426,30218,26730,1383,59672,73928,99950,3050,95868,50002,10474,40772,6080,76991,66610,33955,8094,77059,39511,57306,66008,37833,41970,44416,41990,11774,55342,36728,27065,85951,58347,75100,62837,77693,97901,65373,42758,68676,66452,10473,98095,49785,63189,71642,41310,43974,46393,26333,29750,16222,28194,56752,56607,77122,75474,76244,30717,72911,78280,11341,78006,67006,34610,12801,64451,22548,69710,56261,76894,44716,3328,97340,65473,78017,84645,92948,16484,65241,84687,50375,39717,12516,64247,42705,40806,54534,62714,32103,22186,17703,56440,79807,86697,63554,90495,50965,36359,44464,30680,99708,36124,40417,32948,79552,57395,27384,49626,59051,8152,17600,50408,18658,39718,84313,19480,22953,35421,51316,87188,13734,97103,30071,10172,79054,39113,566,30433,27091,81635,95736,73405,36164,25470,96694,88474,12999,50913,98731,14218,96014,69881,71671,38993,48438,28196,91409,33002,57904,74678,20529,85040,19481,21222,90598,58820,34719,79856,31827,71266,40343,97448,72854,54361,28512,83845,13546,79033,87639,62756,68355,65798,84704,46295,99185,82554,73212,84366,78513,95227,25270,97544,65325,10689,66868,12172,58418,13028,80316,33430,60121,44254,69453,35446,9664,2967,33812,30777,55360,50301,80124,81336,5661,8733,99905,8050,50546,25132,77866,87360,83631,12403,77578,89699,84053,5128,23888,62176,81474,16696,85800,40346,76853,46762,80153,23522,73116,41548,55836,53227,55841,24241,26019,34942,52508,94276,4208,35351,61030,99552,51153,32361,92548,62095,53923,71633,83043,27718,22328,95682,53102,44750,70919,55643,93895,52312,60163,87839,34989,625,86710,48205,77595,10787,64041,74134,6443,69913,41784,160,57114,52510,75720,40533,81922,4074,29936,41664,8786,53387,67266,5180,28498,37558,50673,85883,37748,23123,66460,82821,90897,28478,28735,21729,89351,89650,88603,61645,81576,73162,60388,42576,71577,27630,47729,67637,32327,17781,94534,90902,3675,18009,10656,45683,95025,61867,31363,79488,86938,38857,27824,51373,55650,16060,62198,94917,93637,63981,18701,73319,79301,87973,98970,82667,7817,42855,38205,4154,19716,40876,85131,80614,84099,67951,61472,22028,50861,99170,50623,55245,43257,9259,2046,92502,9608,15685,36195,75578,86041,69103,77206,85070,1878,21470,76703,7047,14622,47468,69198,55361,65885,18457,96521,71981,19974,97097,55423,42199,64113,8399,84769,92003,68457,19874,19674,54445,64630,74713,48050,4846,49366,14656,96909,10582,83720,21491,42325,3535,40032,82140,15231,48725,81094,17483,15625,96194,85723,53950,44448,65451,853,32882,49038,21032,98399,67987,47816,70861,83434,92022,91881,91859,64754,4302,73627,90938,44257,28494,21079,61801,88931,84928,64556,94492,69626,35201,10469,71048,73259,2372,29999,35219,37529,34235,41328,6456,90655,48710,36963,88345,48229,9067,67506,56402,20025,29973,5713,93829,54690,27393,17706,78969,63644,49784,9035,95153,17901,80510,30122,47341,15811,96751,23146,52648,51130,81128,95732,67098,26040,97658,46625,46940,29631,66448,84438,83653,60214,85991,14650,56168,71728,46704,99972,90639,19894,37132,26862,26907,50597,21149,95031,6296,33068,60718,74791,19459,10044,50563,70442,33085,50653,9568,18856,70399,66684,13508,39647,43584,77286,4005,96022,85164,32226,79700,34380,57730,73299,59549,45036,77672,51802,82440,61799,59613,57490,33540,60593,91743,75250,26280,38303,18398,76459,12998,64210,88796,928,88102,7120,71063,62009,54051,90920,48314,15587,65561,29616,27071,21894,85045,28289,38686,69172,51952,39397,58925,33503,13345,40381,41933,6809,46051,32600,29013,67107,32439,33470,4024,11255,55137,96365,16417,83076,96100,33296,69211,60418,87849,33003,81981,32630,81492,76611,8454,95659,86424,67960,83164,79630,80188,56974,11236,75718,58943,77813,5506,53693,47456,84052,84972,18177,14699,45415,13757,22028,15955,10230,63531,67960,20099,14630,5893,69603,5593,18205,71943,98668,61059,19326,7309,69670,13059,44197,59408,19465,47150,2302,39680,66744,62749,94999,72060,82575,6353,83844,79563,24241,78325,54540,58825,65490,28391,53630,92169,32999,81051,7830,69966,1069,66744,94735,49131,3375,68646,63617,29936,75079,78408,56996,56996,58943,23236,52909,39504,4505,73259,13593,55058,90366,21160,24170,49895,35067,58181,30629,60359,79224,72333,6353,52140,99652,21060,93315,3388,61452,91881,97946,52468,50967,12457,87240,61820,3673,8046,33491,82408,75072,92169,38106,3465,97476,48992,92135,26981,54986,87849,90282,19936,58457,98109,92057,54434,91071,66967,1399,85448,17875,92548,55524,24623,82120,68161,47304,61525,80917,58411,16214,18278,89152,20529,64650,26643,44930,23236,30365,58418,37815,72407,61993,25445,68192,2171,52476,39123,63413,86366,69792,853,1764,61819,35857,74104,4846,49000,19481,64214,24500,11613,79733,84492,73051,75143,70524,94362,52641,3384,22286,96038,99403,40343,44083,95955,41038,1476,77895,367,74695,24618,69603,59547,93154,22030,46018,16447,77120,4085,93900,37157,54584,32103,24997,92645,52140,53008,93246,19610,26644,90295,37251,55480,2618,5694,40712,20285,8399,33987,83718,67473,91197,18308,15079,72762,48749,74660,35742,20054,49926,23359,13353,18441,38356,69239,20077,36728,4085,90490,20529,28839,28215,23390,33912,63240,12783,9548,34159,93295,19318,50208,63743,74490,46203,47115,24698,97329,52137,16214,56206,54051,12613,5145,75143,70630,45036,37602,67465,19540,10327,54445,77521,87243,94642,14353,28095,59547,54098,86386,3934,86162,67379,2857,94699,59692,79733,16177,89381,61802,63859,61635,68777,27696,19524,97681,38892,20339,56378,44083,68183,57074,77340,93246,32940,9905,23591,6532,96347,67947,71196,12516,12623,40191,80845,64247,20054,94404,46295,25760,31573,7285,86366,83434,727,25350,27330,1444,30569,33026,69533,36689,97853,19874,32882,98055,8748,14820,84215,8951,79671,83458,12712,9826,99468,48921,74542,53426,62393,34534,14600,90686,58618,29801,97020,99436,72433,43385,66924,85042,61768,96007,55841,82217,92720,85644,70014,61513,83383,35351,36204,53693,65720,13233,54098,74904,99527,17421,87286,73670,87143,56549,17544,49665,83458,86162,76603,29160,17353,44717,72497,56376,98970,35177,87839,9819,19991,99472,95955,6147,41884,22871,87849,89152,68355,1300,78417,7411,90897,17706,96897,25688,26711,18437,727,43362,25589,15578,51717,87917,18773,13575,88345,15329,9703,31667,24146,96947,48749,67273,27673,76002,69394,65901,25041,29259,4302,55342,67181,66448,8945,57264,22953,96694,99403,19601,57125,83242,53532,17353,30772,7681,40905,62893,68362,94612,81466,55342,1991,29259,81894,19933,29160,32353,19524,28036,34263,72881,94735,81998,14983,16498,31530,22353,40972,42758,34614,36599,9788,8500,32246,97000,23658,81094,34436,67181,40954,17439,20012,88564,26907,61851,2302,82527,42862,18308,47922,86826,4413,19986,98564,41201,21731,85783,82055,96332,67785,52508,28735,42671,28175,45412,55814,72252,62216,86933,3446,68901,3934,30569,28889,95821,86519,2820,71543,28075,49821,70640,37529,53797,12621,59740,80678,64812,24496,51645,48178,97404,84181,79466,49012,9821,11994,64940,44081,36009,74425,97000,71651,37768,81902,14533,37764,96098,99878,19844,24275,86835,50487,55814,40413,75143,92801,18856,21032,45628,57904,8046,599,19986,36728,15689,88338,98220,49272,70236,1257,43934,92534,21019,55480,20498,1559,17257,50434,33491,29364,68676,71196,57264,10516,76968,76451,63377,22993,29959,24146,24241,65441,21243,20688,48678,85723,90188,7948,89203,74127,98410,26207,54882,41201,56682,36000,10044,66881,54098,62618,44228,44375,57688,67785,76853,67181,74352,44747,65325,26040,76357,63743,70017,29616,67960,86014,64774,2836,70818,8266,98410,55523,64630,73441,41310,86835,1257,48202,48059,89418,99950,93629,42400,28036,3206,63565,79878,40852,73804,10635,37303,44476,33427,19648,69774,22075,47957,38220,973,73139,76607,9430,42021,44821,37536,21470,23909,52569,61415,91724,69792,98109,40533,69603,68597,88696,87661,73605,26364,80265,77204,74199,46711,44800,20113,13665,68967,83242,1394,18598,23048,96719,50040,69436,78287,13717,57246,4195,73158,62121,4379,77521,38205,14099,36689,50500,72696,70517,53008,92332,96231,25967,50931,25647,69627,18009,4036,45415,74635,48202,28075,16484,80888,92128,80614,78408,38770,42230,5763,71355,83730,19683,56682,17439,38220,97571,85042,37062,37974,43362,96751,63565,34057,8362,12593,80095,63117,45618,83358,57307,19322,73845,74163,2820,29973,82612,67375,28498,67776,16416,62592,99652,99597,37318,24379,52909,2580,66534,51378,30585,18412,79445,526,38819,15715,11365,80862,96719,71577,40974,71404,78296,52718,79043,70737,56610,53102,58925,87176,82598,48610,27903,14533,89077,64113,67379,25169,38819,99585,72696,26364,64754,85528,96751,35448,76747,15033,79931,19906,53486,86870,331,64940,35216,97329,49954,76878,47681,94938,25116,1979,76878,19524,42333,98109,13354,46156,29664,18421,96653,36860,66708,37768,24007,53360,20691,50930,94831,56610,80298,67003,99565,78287,65241,66824,3375,84282,38201,51138,20546,10525,9259,43246,66084,86300,39240,94848,79543,49272,28494,61162,19831,25564,84099,50541,22686,87773,14432,77313,40852,47729,71736,28015,14426,63379,50927,27635,56511,61725,12378,11997,53387,86912,8461,9756,55819,81094,77581,37406,1399,78336,3509,58435,89418,26364,43720,56221,3765,86104,46594,74829,97476,7456,83358,19639,17687,39504,29185,84944,72793,40413,86810,74806,76611,41089,2674,70839,64382,5225,1059,16885,67784,40712,87639,14787,8221,75727,53238,59345,43434,8874,63313,72149,88564,23009,70430,47177,99557,54664,80241,16281,48534,33173,91692,93434,92702,9806,24565,13593,17046,78026,56549,67547,53950,11742,57114,6353,84099,34016,52566,58066,46625,29185,56469,32999,86804,98591,70919,36689,99302,50971,44665,16804,64214,96347,95531,67181,43297,7706,78683,87439,75788,20253,16620,22186,26924,4024,40933,97989,3641,54527,28528,95483,41970,87243,67181,94672,77578,87917,49038,81506,65389,33491,59950,96303,45628,96994,39113,22042,76295,35074,12096,5763,55046,88446,36289,70164,86212,37318,19493,32261,43808,94893,54170,80850,14699,65720,71642,1247,48717,7145,59950,66981,47150,99279,97379,98564,64754,75106,29284,51572,67965,57576,44678,42874,52481,46327,87243,98591,50971,84440,99118,71580,29276,43720,67635,88879,87306,11269,50588,23910,13275,80917,95213,17493,11567,53448,18598,59662,81225,97448,55606,12333,80148,86804,19060,80732,57164,42497,61030,38016,85167,6595,84888,19026,9417,90654,79671,25022,20371,67098,93831,96134,19026,9116,59496,10130,96160,89045,44254,70399,78874,250,2992,30948,99014,68446,35074,90601,8395,83303,99609,4085,50541,19387,98339,83718,75206,20285,18205,8790,93799,97448,38997,82853,84944,63469,53370,40417,63407,58899,86835,42021,21803,22347,70117,18460,39733,3388,49222,23371,10515,76847,37406,81896,53127,6166,64113,4922,74235,50163,13753,31880,21903,96087,8015,50913,97329,97952,85574,80653,44172,50326,23910,4848,12950,99905,16840,65490,18421,19896,13969,82834,73623,14650,45374,89145,87200,69429,43297,77521,79841,97329,4195,10735,13233,9559,69626,973,20339,49890,20688,62077,5212,97476,35190,7940,53230,78477,50782,91626,26142,12828,43214,42705,3813,69774,78087,13191,65373,31326,44703,77768,72346,55841,91480,50266,32120,78857,78087,15262,39586,41506,43879,94189,82373,13636,725,67465,20371,93624,34610,51721,89271,85631,27597,40191,77120,21060,73441,39903,37090,62925,86815,77855,58081,11499,58767,79931,76405,71804,89418,26207,81028,67000,97946,19176,40050,21712,95141,74426,90947,99315,52641,66885,70949,39006,94699,79549,15231,80265,93831,38518,56206,24275,30145,11115,38847,81896,24173,91144,31630,52312,94002,15715,65809,43665,13998,19319,54899,89941,35018,48678,61410,66084,49890,12862,4591,26413,66708,20255,72346,32261,39006,81492,78408,84972,56253,38518,46704,19459,64869,76295,79554,2327,50913,43617,54437,3859,88444,69603,68858,37419,83986,3675,69912,73291,93559,94129,45925,56101,28215,45618,60751,32226,99172,25399,46594,20922,23482,38518,78198,31527,48050,76357,60751,27630,41728,30822,17257,86918,72433,605,48717,30812,49119,53950,84821,37467,51247,11778,75846,6909,39579,56996,49222,1046,75909,85233,11115,48678,82981,38847,44481,20020,48281,37602,79630,21600,12407,61701,99728,7285,79242,94245,17317,50743,29846,22042,99146,98564,94735,48421,36346,73865,34189,20949,69741,22771,95272,55606,26284,97571,66343,61725,69453,53008,14769,9985,34159,538,97476,93799,45890,85783,11314,909,66847,12573,5225,64068,6140,69958,71776,72854,87851,23661,93621,56498,8046,49000,90367,50743,93224,5694,31671,12403,28608,13700,14600,25647,58457,46118,15110,38630,88625,66489,75270,69084,30569,82794,54979,97008,62756,39637,56498,17139,64139,41811,16649,3384,6835,19736,81106,83134,52625,69436,59547,7706,24146,69782,70029,79878,34436,42535,94245,99641,60761,99118,72747,96947,6080,53713,77118,39711,32923,8015,40972,909,52644,40417,25059,14933,98045,29022,39510,86809,65180,94275,94060,88241,63105,82120,52022,31708,81257,68901,23264,70217,51347,1146,51619,96007,68021,43786,37138,86366,80903,973,41987,89115,28528,53238,21019,78342,45121,16281,76405,83859,94303,83131,48244,23422,44144,28494,27014,411,5826,8908,62124,96716,16281,19481,12950,68161,71081,4302,49821,90923,28512,97532,40533,68859,20691,19524,56193,28608,53863,75261,66742,69436,75117,97532,78417,22585,40933,26145,62086,23236,22353,61591,70342,38220,44921,65667,92135,52660,78182,50204,11113,45722,85912,73734,97379,46321,28608,64868,86870,12950,92830,16281,9826,79630,29936,48325,58134,19936,3465,50652,62398,75519,45903,72292,37768,3101,48659,89382,26817,72060,71633,28862,37062,95824,17421,37836,35266,42087,8221,2992,99472,62176,82986,66841,5655,71017,47100,59608,38650,33540,19403,86804,37089,88796,11365,66036,30580,49272,61059,32336,42045,19736,14432,75303,19459,72746,9756,52140,22286,15852,89395,37536,17139,49613,11997,82612,22699,1819,96443,10065,59691,91754,61635,15995,94734,59625,18488,549,17267,54170,84438,97681,92169,39723,40972,70049,21571,50927,97977,2170,34393,30365,84968,36733,52429,89217,98478,19936,57236,52227,682,46190,19493,72252,33071,74425,65880,7176,84230,75727,62179,2618,37619,66848,89941,88796,13176,67181,58467,78999,63090,21086,21380,21054,97858,14820,55360,12593,2992,17905,36600,64119,94276,27651,31437,14234,69699,37764,34393,97858,30822,80264,76935,48633,83287,71017,42497,7120,6986,61192,41310,28175,56752,6396,29342,6166,67316,16953,83502,5906,97448,27897,76885,62460,76991,94002,66318,8797,92332,56284,93895,97591,66722,45036,42459,40915,58114,41687,30822,34625,73623,87849,69480,56610,88446,36599,57490,58467,78074,26207,30122,98853,61433,91860,9703,55134,99652,42855,50002,13354,39216,42456,96322,46704,26911,31667,51444,4154,77313,5895,53072,38680,31896,24038,71943,14511,88345,19906,51551,47304,10423,16885,30210,2334,74029,25863,80732,48957,60751,14630,46693,50487,98850,31860,62482,36963,29259,74490,81971,34057,5593,43197,8945,20922,31896,39123,57576,85814,20253,15262,83358,74075,94489,67316,76603,44083,85912,7176,84944,65447,72632,8908,83963,49613,25022,9430,41955,44514,15971,89145,66841,39984,79461,43617,84438,61525,64327,12727,49546,14858,63002,69488,32922,5574,73475,67441,91812,21451,1069,30175,68674,5888,63342,25761,91716,59239,90247,43756,56607,63340,36491,81490,67441,97000,97329,22800,16281,80991,16484,40933,37764,54534,76357,81257,81812,7464,81028,13593,71543,11460,14099,71633,61977,98850,42891,99302,12157,77303,46018,80148,74793,28847,57306,65633,73635,682,97591,1454,530,96134,89152,73090,77579,5574,51832,19524,33348,96719,239,38050,74035,87176,36994,11616,42811,73408,70052,21803,56265,12792,70704,86366,2315,32088,37140,8454,46482,78182,82359,46018,12914,75826,67128,13546,35962,83434,76935,42045,17738,69639,16840,95005,79321,65809,98478,14123,53684,13779,4922,33781,34263,28175,10735,30429,33290,48059,60044,10130,19026,27306,57296,37303,57114,8775,33718,34471,91751,20546,16885,7007,32922,42407,97000,37376,67089,640,80843,13340,80241,23910,23482,18741,29022,12652,9679,76295,47304,58066,80614,76357,80084,70342,49895,83639,31527,80265,16456,75788,54295,55423,67776,85082,94641,3398,26943,33029,55841,24630,31361,80870,13665,63090,46547,77340,21729,77340,17706,85912,96909,43162,59711,58825,22043,86365,3446,19906,87849,28735,35281,91173,52137,53997,96347,47150,81971,30753,59826,58277,35899,16234,9713,89509,54434,79807,18421,37981,3813,12172,13925,33287,60114,97355,96454,62198,14426,69774,90366,73441,86809,69173,41636,88289,50002,27718,57663,78902,87147,83720,24275,37602,5644,44926,14787,11477,47348,53185,97532,31671,94938,10787,22487,44772,30581,19639,92645,682,83730,70949,70256,94362,18119,77059,53713,99864,76407,30569,93295,28054,88199,61645,65258,44856,16222,93066,1069,35495,35216,71139,70565,59950,19189,80614,79406,78017,50588,39988,59488,86815,61525,68230,81857,12182,68021,19844,35327,41687,91356,82217,21309,57114,72578,66640,91356,30717,36994,79628,31708,30158,96684,40546,46547,77024,77843,9000,67181,19714,40972,97858,77206,50822,79543,30348,44930,36998,79466,70342,79543,91716,44254,93629,93154,9268,2327,25688,26644,34919,49585,8122,33992,61701,63386,70430,87574,99905,80316,38224,56253,79074,3065,76892,40852,93051,26663,54434,73331,39702,27718,87895,66326,83844,94699,36837,66847,96365,89822,99369,6909,44281,8094,20829,56549,52682,7748,61994,75727,18441,51347,6147,46563,77059,41703,33956,65373,82794,9756,85814,97319,36078,43509,26924,41987,63054,94612,38635,86815,81508,48314,96897,24651,52867,61993,76968,54170,24016,51288,94641,86405,80151,78237,83369,78685,69602,17421,6532,97474,6080,12394,60179,73748,93339,17210,67089,82868,89729,52829,86897,63564,31437,88796,12043,64659,75143,2151,19459,26101,95868,64868,90341,97532,54589,65389,88616,16060,52566,2618,22032,15246,77625,8690,94303,84821,88999,11997,20922,59571,93154,90750,73474,61672,51526,49160,64630,35319,98793,23284,78584,83162,70342,90583,37815,95483,98027,80873,89382,21160,76407,62663,2046,70246,77579,98027,1458,38048,32353,17439,43954,18308,19405,7748,19481,20557,81357,99088,1300,67176,20922,71728,61415,40217,93900,48992,72407,44481,80871,65554,13742,63117,30812,78857,5694,32922,56784,56549,93475,88320,38630,28735,69699,42035,6700,40838,7421,99712,19459,45270,79700,13308,90803,97343,53630,23764,37536,35018,68367,74044,85303,9417,65440,74878,19548,42045,91095,5506,36165,61802,48717,67107,26551,24651,35281,94848,98045,28617,3398,9548,16456]

    # for i in range(len(nums), 0, -1):
    #     print(i)
    s = Solution()

    print(s.medianOfUniquenessArray(nums))
    # print(s.medianOfUniquenessArray([1,2,3]))